package basic.study.leetcode;

/**
 * @ClassName Mid62
 * @Description 不同路径
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/23 12:12
 * @Version 1.0
 */
public class Mid62 {
    /**
     * 想到的解法：bfs、dfs、dp，用dp做
     */
    class Solution {
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            for (int i=0; i<m; i++) dp[i][0] = 1;
            for (int i=0; i<n; i++) dp[0][i] = 1;
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }

    static class Solution1 {
        int sum = 0;
        public int uniquePaths(int m, int n) {
            dfs(m, n, 0, 0);
            return sum;
        }

        public void dfs(int m, int n, int curX, int curY) {
            //剪枝
            if (curX >= m || curY >= n) {
                return;
            }
            //到达
            if (curX == m-1 && curY == n-1) {
                sum++;
                return;
            }
            //dfs
            dfs(m, n, curX+1, curY);
            dfs(m, n, curX, curY+1);
        }
    }

    public static void main(String[] args) {
        Solution1 s = new Solution1();
        System.out.println(s.uniquePaths(7, 3));
    }
}
